#include "binaryTree.h"

BTNode* createBTNode(dataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

void preOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	preOrder(root->left);
	preOrder(root->right);
}

void inOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	inOrder(root->left);
	printf("%d ", root->data);
	inOrder(root->right);
}

void postOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	postOrder(root->left);
	postOrder(root->right);
	printf("%d ", root->data);
}

void levelOrder(BTNode* root)
{
	assert(root);
	Queue que;
	initQueue(&que);
	pushQueue(&que, root);

	while (!emptyQueue(&que))
	{
		BTNode* front = queueFront(&que);
		popQueue(&que);
		printf("%d ", front->data);
		if(front->left)
			pushQueue(&que, front->left);
		if (front->right)
			pushQueue(&que, front->right);
	}
	queueDestroy(&que);
}


int treeSize(BTNode* root)
{
	if (root == NULL) {
		return 0;
	}
	return treeSize(root->left) + treeSize(root->right) + 1;
}

int treeLevel(BTNode* root, int k)
{
	assert(k > 0);

	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	
	return treeLevel(root->left, k - 1) + treeLevel(root->right, k - 1);
}

int treeHeight(BTNode* root)
{
	if (root == NULL) {
		return 0;
	}
	int leftNum = treeHeight(root->left) + 1;
	int rightNum = treeHeight(root->right) + 1;
	return leftNum > rightNum ? (leftNum) : (rightNum);
}

BTNode* findBTNode(BTNode* root, dataType x)
{
	if (root == NULL)return NULL;
	if (root->data == x)
		return root;
	BTNode* lret = findBTNode(root->left, x);
	if (lret && lret->data == x)return lret;
	BTNode* rret = findBTNode(root->right, x);
	if (rret && rret->data == x)return rret;

	return NULL;
}

bool isCompleteBinaryTree(BTNode* root)
{
	assert(root);
	Queue que;
	initQueue(&que);
	pushQueue(&que, root);

	while (!emptyQueue(&que))
	{
		BTNode* front = queueFront(&que);
		popQueue(&que);
		if (front)
		{
			pushQueue(&que, front->left);
			pushQueue(&que, front->right);
		}
		if (front == NULL) {
			break;
		}
	}
	while (!emptyQueue(&que)) {
		BTNode* front = queueFront(&que);
		popQueue(&que);
		if (front) {
			queueDestroy(&que);
			return false;
		}
	}
	queueDestroy(&que);
	return true;
}

void destroyBinaryTree(BTNode* root)
{
	if (root == NULL) {
		return;
	}
	destroyBinaryTree(root->left);
	destroyBinaryTree(root->right);
	//printf("The %d has been destroyed!\n", root->data);
	free(root);
	root = NULL;
}
